package datastructure.book.dp._1_pathway.all;

import org.junit.jupiter.api.Test;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;

public class _7_Solution {

    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        int cnt = 0;
        LinkedList<int[]> list = new LinkedList<>();
        list.add(new int[]{start,fuel});
        while (!list.isEmpty()) {
            int[] ints = list.removeFirst();
            int index = ints[0];
            int oilAll = ints[1];
            for (int i = 0; i < locations.length; i++) {
                if (i == index) {
                    continue;
                }
                int oil = oilAll-Math.abs(locations[i]-locations[index]);
                if (oil < 0) {
                    continue;
                } else {
                    if (i == finish) {
                        cnt++;
                    }
                    if (oil == 0) {
                        continue;
                    }
                    int[] arr = new int[]{i,oil};
                    list.add(arr);
                }
            }
        }
        if (start == finish) {
            cnt++;
        }
        return cnt%(1000000000+7);
    }
    int[][] cntArr;
    public int countRoutes2(int[] locations, int start, int finish, int fuel) {
        cntArr = new int[locations.length][fuel+1];
        for (int[] ints : cntArr) {
            Arrays.fill(ints, -1);
        }
        return countRoutes0(locations,start,finish,fuel);
    }

    private int countRoutes0(int[] locations, int start, int finish, int fuel) {
        if (cntArr[start][fuel] != -1) {
            return cntArr[start][fuel];
        }
        int cnt = (start==finish?1:0);
        for (int i = 0; i < locations.length; i++) {
            if (i == start) {
                continue;
            }
            int oil = fuel-(Math.abs(locations[i]-locations[start]));
            if (oil < 0) {
                continue;
            }
            if (oil == 0 && i == finish) {
                cnt++;
                continue;
            }
            int nextCnt = countRoutes0(locations,i,finish,oil);
            cntArr[i][oil] = nextCnt;
            cnt+=nextCnt;
            cnt%=1000000007;
        }
        return cnt;
    }

    @Test
    public void test(){
        int[] loc = {2,3,6,8,4};
        System.out.println(countRoutes2(loc,1,3,5));
    }

    public int countRoutes3(int[] locations, int start, int finish, int fuel){
        int[][] f = new int[fuel+1][locations.length];
        for (int[] ints : f) {
            ints[finish] = 1;
        }
        for (int i = 1; i < f.length; i++) {
            for (int j = 0; j < f[i].length; j++) {
                if (i < Math.abs(locations[finish] - locations[j])) {
                    continue;
                }
                for (int k = 0; k < locations.length; k++) {
                    if (k == j) {
                        continue;
                    }
                    int oil = Math.abs(locations[j]-locations[k]);
                    if (i < oil) {
                        continue;
                    }
                    f[i][j] += f[i-oil][k];
                    f[i][j]%=1000000007;
                }
            }
        }
        return f[fuel][start];
    }
    @Test
    public void testCountRoutes3(){
        int[] loc = {2,3,6,8,4};
        System.out.println(countRoutes2(loc,1,3,5));
        System.out.println(countRoutes3(loc,1,3,5));
    }

}
